package com.cty._03_SolutionSeekingMindset._33_SequenceOfBST;

/**
 * @Auther: cty
 * @Date: 2020/7/13 8:57
 * @Description: 面试题33：二叉搜索树的后序遍历序列
 * 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
 * @version: 1.0
 */
public class SequenceOfBST {

    public static boolean verifyOfBST(int[] sequence, int start, int end){
        if(sequence==null || (end-start+1)<=0)
            return false;

        int root = sequence[end];

        int i = start;
        for(; i<end; i++)
            if(sequence[i] > root)
                break;

        int j = i;
        for(; j<end; j++)
            if(sequence[j] < root)
                return false;

        // 判断左子树是不是二叉搜索树
        boolean left = true;
        if(i > start)  // 有左子树
            left = verifyOfBST(sequence, start, i-1);

        // 判断右子树是不是二叉搜索树
        boolean right = true;
        if(i < end)  // 有右子树
            right = verifyOfBST(sequence, i, end-1);

        return left && right;
    }  // end verifyOfBST

}  // end class
